{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Ones and Zeroes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaxForm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #一和零"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制字符串数组 <code>strs</code> 和两个整数 <code>m</code> 和 <code>n</code> 。</p>\n",
    "\n",
    "<div class=\"MachineTrans-Lines\">\n",
    "<p class=\"MachineTrans-lang-zh-CN\">请你找出并返回 <code>strs</code> 的最大子集的长度，该子集中 <strong>最多</strong> 有 <code>m</code> 个 <code>0</code> 和 <code>n</code> 个 <code>1</code> 。</p>\n",
    "\n",
    "<p class=\"MachineTrans-lang-zh-CN\">如果 <code>x</code> 的所有元素也是 <code>y</code> 的元素，集合 <code>x</code> 是集合 <code>y</code> 的 <strong>子集</strong> 。</p>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [\"10\", \"0001\", \"111001\", \"1\", \"0\"], m = 5, n = 3\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最多有 5 个 0 和 3 个 1 的最大子集是 {\"10\",\"0001\",\"1\",\"0\"} ，因此答案是 4 。\n",
    "其他满足题意但较小的子集包括 {\"0001\",\"1\"} 和 {\"10\",\"1\",\"0\"} 。{\"111001\"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [\"10\", \"0\", \"1\"], m = 1, n = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>最大的子集是 {\"0\", \"1\"} ，所以答案是 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= strs.length &lt;= 600</code></li>\n",
    "\t<li><code>1 &lt;= strs[i].length &lt;= 100</code></li>\n",
    "\t<li><code>strs[i]</code>&nbsp;仅由&nbsp;<code>'0'</code> 和&nbsp;<code>'1'</code> 组成</li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ones-and-zeroes](https://leetcode.cn/problems/ones-and-zeroes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ones-and-zeroes](https://leetcode.cn/problems/ones-and-zeroes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"10\",\"0001\",\"111001\",\"1\",\"0\"]\\n5\\n3', '[\"10\",\"0\",\"1\"]\\n1\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        N = len(strs)\n",
    "        def count(s):\n",
    "            zeroes = 0\n",
    "            ones = 0\n",
    "            for c in s:\n",
    "                if c == '0':\n",
    "                    zeroes += 1\n",
    "                else:\n",
    "                    ones += 1\n",
    "            return (zeroes, ones)\n",
    "        counts = [count(x) for x in strs]\n",
    "\n",
    "        @cache\n",
    "        def recur(i, remainZeroes, remainOnes):\n",
    "            if i == N:\n",
    "                return 0\n",
    "            \n",
    "            res = recur(i + 1, remainZeroes, remainOnes)\n",
    "            zeroes, ones = counts[i]\n",
    "            if zeroes <= remainZeroes and ones <= remainOnes:\n",
    "                res = max(res, 1 + recur(i + 1, remainZeroes - zeroes, remainOnes - ones))\n",
    "            return res\n",
    "        return recur(0, m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs, m, n):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :type m: int\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = [[0]*(n+1) for x in range(m+1)]\n",
    "        for str in strs:\n",
    "            zeros = str.count('0')\n",
    "            ones = str.count('1')\n",
    "            for i in range(m, zeros-1, -1):\n",
    "                for j in range(n, ones-1, -1):\n",
    "                    dp[i][j] = max(dp[i-zeros][j-ones]+1, dp[i][j])\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for strs_item in strs:\n",
    "            item_count0 = strs_item.count('0')\n",
    "            item_count1 = strs_item.count('1')\n",
    "\n",
    "            # 遍历可容纳的背包\n",
    "            for i in range(m, item_count0 - 1, -1):\n",
    "                for j in range(n, item_count1 - 1, -1):\n",
    "                    dp[i][j] = max(dp[i][j], 1 + dp[i - item_count0][j - item_count1])\n",
    "\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "         \n",
    "        def count_zeros_and_ones(string):\n",
    "            zeros, ones = 0, 0\n",
    "            for char in string:\n",
    "                 if char ==\"0\":\n",
    "                     zeros+=1\n",
    "                 if char ==\"1\":\n",
    "                     ones+=1\n",
    "            return zeros, ones\n",
    "        dp = [ [0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "\n",
    "        for string in strs:\n",
    "            zeros, ones = count_zeros_and_ones(string)\n",
    "            for i in range(m, zeros-1, -1):\n",
    "                for j in range(n, ones-1, -1):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)\n",
    "\n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "\n",
    "        def extract(s):\n",
    "            cnt = Counter(s)\n",
    "            return cnt['1'], cnt['0']\n",
    "\n",
    "\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "\n",
    "        for s in strs:\n",
    "            one, zero = extract(s)\n",
    "            for i in range(m, zero - 1, - 1):\n",
    "                for j in range(n, one - 1, -1):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-zero][j-one] + 1)\n",
    "        return max(dp[-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "#         dic = defaultdict(int)\n",
    "#         ma = 0\n",
    "\n",
    "#         dic[(m, n)] = 0\n",
    "#         for s in strs:\n",
    "#           l, zeros = len(s), s.count('0')\n",
    "#           copy = dic.copy()\n",
    "#           for a, b in copy:\n",
    "#             if a >= zeros and b >= l - zeros and copy[(a, b)] + 1 > dic[(a - zeros, b - l + zeros)]:\n",
    "#               dic[(a - zeros, b - l + zeros)] = copy[(a, b)] + 1\n",
    "#               if copy[(a, b)] + 1 > ma:\n",
    "#                 ma = copy[(a, b)] + 1\n",
    "#         return ma\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        all = []\n",
    "        for s in strs:\n",
    "            one=s.count('1')\n",
    "            all.append([len(s)-one,one])\n",
    "        f = [[{} for _ in range(n+1)] for _ in range(m+1)]\n",
    "        l = len(all)\n",
    "        all.sort()\n",
    "\n",
    "        def dfs(i, m, n):\n",
    "            if i in f[m][n]:\n",
    "                return f[m][n][i]\n",
    "            if i == l or all[i][0] > m:\n",
    "                return 0\n",
    "            if all[i][1] > n:\n",
    "                ans = 0\n",
    "            else:\n",
    "                ans = 1+dfs(i+1, m-all[i][0], n-all[i][1])\n",
    "            right = all[i][1]\n",
    "            for j in range(i+1, l):\n",
    "                if all[j][1] < right:\n",
    "                    ans = max(ans, dfs(j, m, n))\n",
    "                    right = all[j][1]\n",
    "            f[m][n][i] = ans\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        # 存两个维度，分别表示0,1个数\n",
    "        N = 1000\n",
    "        dp = [[0 for i in range(N)]for j in range(N)]\n",
    "        for str_1 in strs:\n",
    "            x = str_1.count('0')\n",
    "            y = str_1.count('1')\n",
    "\n",
    "            for i in range(m, x - 1, -1):\n",
    "                for j in range(n, y - 1, -1):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - x][j- y] + 1)\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs, m, n):\n",
    "        length = len(strs)\n",
    "        dp = []\n",
    "        \n",
    "        for i in range(0, 1100):\n",
    "            dp.append([])\n",
    "            for j in range(0, 1100):\n",
    "                dp[i].append(0)\n",
    "                \n",
    "        dp[0][0] = 0\n",
    "        \n",
    "        for s in strs:\n",
    "            a = s.count('0')\n",
    "            b = s.count('1')\n",
    "            \n",
    "            for j in range(m, -1, -1):\n",
    "                for z in range(n, -1, -1):\n",
    "                    if (j >= a) and (z >= b):\n",
    "                        dp[j][z] = max(dp[j-a][z-b]+1, dp[j][z])\n",
    "                        \n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        \"\"\"\n",
    "        1. 这道题求的是，从strs数组中取最多个str，这些str中0和1的个数总和不能大于m和n；\n",
    "        2. strs相当于商品列表；每个商品的价值是1；每个商品的重量就是其中0和1的个数；\n",
    "        背包的的容量是m个0和n个1；\n",
    "        3. 本题背包容量是从2个维度来计算的，即总容量 m个0和n个1；\n",
    "        4. dp[i][j] 代表i个0和j个1，最多能从strs中选出来的满足条件str个数。\n",
    "        :param strs: 字符串列表\n",
    "        :param m: 最多m个0\n",
    "        :param n: 最多n个1\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        # dp[i][j] 代表i个0和j个1，最多能组成的子集的个数。\n",
    "        # dp = np.zeros((m+1, n+1), dtype=int)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        # 商品正序遍历\n",
    "        for string in strs:\n",
    "\n",
    "            # 统计单个商品的重量，即0和1的个数\n",
    "            zero_num = string.count(\"0\")\n",
    "            one_num = string.count(\"1\")\n",
    "\n",
    "            # 背包容量倒序遍历\n",
    "            # 当前容量小于zero_num和one_num，到达zero_num或one_num时退出循环，因为至少要保证容量能放下当前string\n",
    "            for i in range(m, zero_num-1, -1):\n",
    "                for j in range(n, one_num-1, -1):\n",
    "                    # 这里与普通的01背包类似\n",
    "                    # 1. 不选当前str，那么01容量还剩dp[i][j]\n",
    "                    # 2. 选当前str，那么01容量还剩dp[i-zero_num][j-one_num]，同时个数要 +1\n",
    "                    # 则dp[i][j]就是容量为i和j时，取两种情况的最大值\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-zero_num][j-one_num] + 1)\n",
    "\n",
    "        return int(dp[m][n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np \n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        def count(s: str) -> list:\n",
    "            ans = [0, 0]\n",
    "            for i in s:\n",
    "                if i == '0':\n",
    "                    ans[0] += 1\n",
    "                else:\n",
    "                    ans[1] += 1\n",
    "            return ans\n",
    "\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for s in strs:\n",
    "            a, b = count(s)\n",
    "            for i in range(m, a-1, -1):\n",
    "                for j in range(n, b-1, -1):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-a][j-b] + 1)\n",
    "\n",
    "        return dp[m][n]\n",
    "\n",
    "\n",
    "    def count_zeros_ones(self, s):\n",
    "        zeros_sum = 0\n",
    "        ones_sum = 0\n",
    "        for s_ in s:\n",
    "            if s_ == '0':\n",
    "                zeros_sum += 1\n",
    "            else:\n",
    "                ones_sum += 1\n",
    "\n",
    "        return zeros_sum, ones_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cost = []\n",
    "        self.memo = dict()\n",
    "\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        cost = [(\n",
    "            sum(\n",
    "                map(\n",
    "                    lambda ch: 1 if ch == '0' else 0,\n",
    "                    ele\n",
    "                )),\n",
    "            sum(\n",
    "                map(\n",
    "                    lambda ch: 0 if ch == '0' else 1,\n",
    "                    ele\n",
    "                )),\n",
    "        ) for ele in strs]\n",
    "        self.cost = cost\n",
    "        self.memo = dict()\n",
    "        return self.recursive(0, m, n)\n",
    "\n",
    "    def recursive(self, i, m, n):\n",
    "        if i == len(self.cost):\n",
    "            return 0\n",
    "\n",
    "        if (m, n) in self.memo:\n",
    "            if i in self.memo.get((m, n)):\n",
    "                return self.memo.get((m, n)).get(i)\n",
    "\n",
    "        if (m - self.cost[i][0]) >= 0 and (n - self.cost[i][1]) >= 0:\n",
    "            choose = self.recursive(i + 1, m - self.cost[i][0], n - self.cost[i][1]) + 1\n",
    "        else:\n",
    "            choose = 0\n",
    "        not_choose = self.recursive(i + 1, m, n)\n",
    "        ans = max(choose, not_choose)\n",
    "        if (m, n) not in self.memo:\n",
    "            self.memo[(m, n)] = dict()\n",
    "        self.memo.get((m, n))[i] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        strs.sort()\n",
    "        length=[0]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def backtrack(start,currentlength,all0,all1):\n",
    "            if start == len(strs):return\n",
    "            for i in range(start,len(strs)):\n",
    "                if i>start and strs[i]==strs[i-1]:continue\n",
    "                c0=strs[i].count('0')\n",
    "                c1=len(strs[i])-c0\n",
    "                if all0+c0<=m and all1+c1<=n:\n",
    "                    currentlength+=1\n",
    "                    length[0]=max(length[0],currentlength)\n",
    "                    backtrack(i+1,currentlength,all0+c0,all1+c1)\n",
    "                    currentlength-=1\n",
    "            return\n",
    "        backtrack(0,0,0,0)\n",
    "        return length[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        # 2D array to 1D array:\n",
    "        count = [(x.count('0'), x.count('1')) for x in strs]\n",
    "        dp = [[0] * ((m+1)*(n+1)) for _ in range(len(strs)+1)]\n",
    "        width = len(dp[0])\n",
    "        for i in range(1, len(strs)+1):\n",
    "            for j in range(width):\n",
    "                cur_m = j // (n+1)\n",
    "                cur_n = j % (n+1)\n",
    "                old_m = cur_m - count[i-1][0]\n",
    "                old_n = cur_n - count[i-1][1]\n",
    "                if old_m >=0 and old_n >=0:\n",
    "                    old_2D = old_m *(n+1) + old_n\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][old_2D]+1) \n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        return dp[len(strs)][width-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        l=len(strs)\n",
    "        counters=[Counter(s) for s in strs]\n",
    "        dp=[[[0]*(l+1) for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                for k in range(1,l+1):\n",
    "                    dp[i][j][k]=dp[i][j][k-1]\n",
    "                    x=i-counters[k-1]['0']\n",
    "                    y=j-counters[k-1]['1']\n",
    "                    if x>=0 and y>=0:\n",
    "                        dp[i][j][k]=max(dp[i][j][k],dp[x][y][k-1]+1)\n",
    "        return dp[m][n][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        def str01num(str):\n",
    "            n0=n1=0\n",
    "            for i in str:\n",
    "                if i=='0': n0+=1\n",
    "                else: n1+=1\n",
    "            return n0,n1\n",
    "        l=len(strs)\n",
    "        dp=[[[0]*(m+1) for _ in range(n+1)] for _ in range(l+1)]\n",
    "        for i,x in enumerate(strs):\n",
    "            n0,n1=str01num(x)\n",
    "            for c1 in range(n+1):\n",
    "                if c1<n1:\n",
    "                    dp[i+1][c1]=dp[i][c1]\n",
    "                else:\n",
    "                    for c2 in range(m+1):\n",
    "                        if c2<n0:\n",
    "                            dp[i+1][c1][c2]=dp[i][c1][c2]\n",
    "                        else:\n",
    "                            dp[i+1][c1][c2]=max(dp[i][c1][c2],dp[i][c1-n1][c2-n0]+1)\n",
    "        return dp[l][n][m]\n",
    "        '''dp=[[0]*(m+1) for _ in range(n+1)]\n",
    "        for x in strs:\n",
    "            n0=x.count('0')\n",
    "            n1=x.count('1')\n",
    "            for c1 in range(n,n1-1,-1):\n",
    "                for c0 in range(m,n0-1,-1):\n",
    "                    dp[c1][c0]=max(dp[c1][c0],dp[c1-n1][c0-n0]+1)\n",
    "        return dp[n][m]'''\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        strs_ct = []\n",
    "        for i, string in enumerate(strs):\n",
    "            nums = list(map(int, string))\n",
    "            strs_ct.append((len(nums)-sum(nums), sum(nums)))\n",
    "\n",
    "        l = len(strs)\n",
    "        dp = [[[0 for _ in range(l)] for _ in range(n+1)] for _ in range(m+1)]\n",
    "\n",
    "        for k in range(l):\n",
    "            for i in range(m+1):\n",
    "                for j in range(n+1):\n",
    "                    if k == 0:\n",
    "                        dp[i][j][k] = 1 if (strs_ct[k][0] <= i and strs_ct[k][1] <= j) else 0\n",
    "                    elif strs_ct[k][0] <= i and strs_ct[k][1] <= j:\n",
    "                        dp[i][j][k] = max(dp[i-strs_ct[k][0]][j-strs_ct[k][1]][k-1]+1, dp[i][j][k-1])\n",
    "                    else:\n",
    "                        dp[i][j][k] = dp[i][j][k-1]\n",
    "        return dp[-1][-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        dp=[[[0 for i in range(n+1)] for j in range(m+1)] for k in range(len(strs)+1)]\n",
    "        for k in range(1,len(strs)+1):\n",
    "            for i in range(0,m+1):\n",
    "                for j in range(0,n+1):\n",
    "                    \n",
    "                    stmp=strs[k-1]\n",
    "                    ct0=stmp.count('0')\n",
    "                    ct1=len(stmp)-ct0\n",
    "                    dp[k][i][j]=dp[k-1][i][j]\n",
    "                    if i-ct0>=0 and j-ct1>=0:\n",
    "                        dp[k][i][j]=max(dp[k][i][j], dp[k-1][i-ct0][j-ct1]+1)\n",
    "        # print(dp[3][1][1])\n",
    "        # print(dp[2][1][0])\n",
    "        return dp[-1][-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        p = len(strs)\n",
    "        # 一般 dp 起始 都是 容量0，物品1\n",
    "        # 这里可以 0 开始，方便初始化\n",
    "        dp = [[[0] * (m+1) for i in range(n+1)] for j in range(p+1)]\n",
    "        \n",
    "        for i in range(n+1):\n",
    "            for j in range(m+1):\n",
    "                dp[0][i][j] = 0\n",
    "        \n",
    "        for i in range(1, p+1):\n",
    "            for j in range(n+1):\n",
    "                for k in range(m+1):\n",
    "                    count_0 = strs[i-1].count(\"0\")\n",
    "                    count_1 = strs[i-1].count(\"1\")\n",
    "                    dp[i][j][k] = dp[i-1][j][k]\n",
    "                    if count_1 <= j and count_0 <= k :\n",
    "                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-count_1][k-count_0]+1)\n",
    "        return dp[p][n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        def zerosandones(strs):\n",
    "            zeros = 0\n",
    "            ones = 0\n",
    "            for s in strs:\n",
    "                if s==\"1\":\n",
    "                    ones += 1\n",
    "                else:\n",
    "                    zeros += 1\n",
    "            return zeros,ones\n",
    "        def f(strs,i,z,o,dp):\n",
    "            if i==len(strs):\n",
    "                return 0\n",
    "            if dp[i][z][o]!=-1:\n",
    "                return dp[i][z][o]\n",
    "            p1 = f(strs,i+1,z,o,dp)\n",
    "            p2 = 0\n",
    "            zeros,ones = zerosandones(strs[i])\n",
    "            if zeros<=z and ones <= o:\n",
    "                p2 = 1+f(strs,i+1,z-zeros,o-ones,dp)\n",
    "            ans = max(p1,p2)\n",
    "            dp[i][z][o] = ans\n",
    "            return ans \n",
    "        dp = [[[-1 for _ in range(n+1)] for _ in range(m+1)] for _ in range(len(strs))]\n",
    "        return f(strs,0,m,n,dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        res = []\n",
    "\n",
    "        dp = [\n",
    "                [\n",
    "                    [0 for _ in range(n+10)]\n",
    "\n",
    "                    for _ in range(m+10)\n",
    "                ]\n",
    "                for _ in range(len(strs) + 10)\n",
    "        ]\n",
    "        for i in range(1,len(strs)+1):\n",
    "            item = strs[i-1]\n",
    "            zeros_cnt = item.count(\"0\")\n",
    "            ones_cnt = item.count(\"1\")\n",
    "            for j in range(m+1):\n",
    "                for k in range(n+1):\n",
    "                    dp[i][j][k] = dp[i-1][j][k]\n",
    "                    if j - zeros_cnt >= 0 and k - ones_cnt >= 0:\n",
    "                        dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-zeros_cnt][k-ones_cnt]+1)\n",
    "        return dp[len(strs)][m][n]\n",
    "        \n",
    "        # @lru_cache(None)\n",
    "        # def dfs(m,n,index,temp):\n",
    "        #     if index == len(strs):\n",
    "        #         res.append(temp[:])\n",
    "        #         return\n",
    "        #     # 要\n",
    "        #     item = strs[index]\n",
    "        #     zeros_cnt = item.count(\"0\")\n",
    "        #     ones_cnt = item.count(\"1\")\n",
    "        #     if m - zeros_cnt >= 0 and n - ones_cnt >=0 :\n",
    "        #         temp.append(strs[index])\n",
    "        #         dfs(m-zeros_cnt,n-ones_cnt,index+1,temp)\n",
    "        #         temp.pop()\n",
    "        #     # 不要\n",
    "        #     dfs(m,n,index+1,temp)\n",
    "        # dfs(m,n,0,[])\n",
    "        # return max([len(i) for i in res])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        nums = []\n",
    "        length = len(strs)\n",
    "        for i in range(length):\n",
    "            x = strs[i]\n",
    "            count_0, count_1 = 0, 0\n",
    "            for j in range(len(x)):\n",
    "                if x[j] == '0':\n",
    "                    count_0 += 1\n",
    "                else:\n",
    "                    count_1 += 1\n",
    "            nums.append([count_0,count_1])\n",
    "        print(nums)\n",
    "        import numpy as np\n",
    "        dp = [[[0 for i in range(n+1)] for j in range(m+1)] for k in range(length)]\n",
    "        for j in range(m+1):\n",
    "            for k in range(n+1):\n",
    "                if j >= nums[0][0] and k >= nums[0][1]:\n",
    "                    dp[0][j][k] = 1\n",
    "        for i in range(1, length):\n",
    "            for j in range(m + 1):\n",
    "                for k in range(n + 1):\n",
    "                    if  nums[i][0] <= j and nums[i][1] <= k:\n",
    "                        dp[i][j][k] = max(dp[i-1][j-nums[i][0]][k - nums[i][1]] + 1, dp[i-1][j][k])\n",
    "                    else:\n",
    "                        dp[i][j][k] = dp[i-1][j][k]\n",
    "        return dp[length - 1][m][n]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        length = len(strs)\n",
    "        dp = [[[0 for _ in range(n+1)] for _ in range(m+1)] for _ in range(length+1)]\n",
    "\n",
    "        # for i in range(length):\n",
    "        #     index = i + 1\n",
    "        for i in range(1, length+1):\n",
    "            index = i-1\n",
    "            str_i = strs[index]\n",
    "            zeros, ones = str_i.count('0'), str_i.count('1')\n",
    "            # dp[i][zeros][ones] = 1\n",
    "\n",
    "            for j in range(m+1):\n",
    "                for k in range(n+1):\n",
    "                    if j - zeros >= 0 and k - ones >= 0:\n",
    "                        dp[i][j][k] = max(dp[i-1][j-zeros][k-ones]+1, dp[i-1][j][k], 1)\n",
    "                    else:\n",
    "                        dp[i][j][k] = dp[i-1][j][k]\n",
    "        return dp[-1][-1][-1]\n",
    "\n",
    "                    \n",
    "\n",
    "        #方法1 三维dp\n",
    "        # length = len(strs)\n",
    "        # dp = np.zeros((length+1, m+1, n+1))\n",
    "        # #循环迭代\n",
    "        # for i in range(1, length+1):\n",
    "        #     count_zeros, count_ones = strs[i-1].count('0'), strs[i-1].count('1')\n",
    "        #     for j in range(m+1):\n",
    "        #         for k in range(n+1):\n",
    "        #             # print(i,j,k,)\n",
    "        #             if count_zeros <= j and count_ones <= k:\n",
    "        #                 dp[i][j][k] = max(dp[i-1][j-count_zeros][k-count_ones] + 1, dp[i-1][j][k])\n",
    "        #             else:\n",
    "        #                 dp[i][j][k] = dp[i-1][j][k]\n",
    "        # return int(dp[-1][-1][-1])\n",
    "\n",
    "        ##方法2 二维DP\n",
    "        # length = len(strs)\n",
    "        # dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        # #dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "        # for i in range(length):\n",
    "        #     zeros, ones = strs[i].count('0'), strs[i].count('1')\n",
    "        #     for j in range(m, zeros-1,-1):\n",
    "        #         for k in range(n, ones-1,-1):\n",
    "        #             dp[j][k] = max(dp[j - zeros][k - ones] + 1, dp[j][k])\n",
    "        # return dp[-1][-1]\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        dp = [[[0] * (n+1) for _ in range(m+1)] for _ in range(len(strs)+1)]\n",
    "        \n",
    "        for i in range(1, len(strs)+1):\n",
    "            oneNum = 0\n",
    "            zeroNum = 0\n",
    "            for ch in strs[i-1]:  # Note: there's an offset of 1\n",
    "                if ch == '0':\n",
    "                    zeroNum += 1\n",
    "                else:\n",
    "                    oneNum += 1\n",
    "            \n",
    "            for j in range(m+1):\n",
    "                for k in range(n+1):\n",
    "                    if j >= zeroNum and k >= oneNum:\n",
    "                        dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zeroNum][k-oneNum] + 1)\n",
    "                    else:  # Cannot fit the current string strs[i-1]\n",
    "                        dp[i][j][k] = dp[i-1][j][k]\n",
    "        \n",
    "        return dp[len(strs)][m][n]\n",
    "                        \n",
    "                        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        counter = [collections.Counter(x) for x in strs]\n",
    "        cache = {}\n",
    "        k = len(counter)\n",
    "        ans = self.recur(counter, cache, k - 1, m, n)\n",
    "        return ans\n",
    "\n",
    "    def recur(self, counter, cache, i, m, n):\n",
    "        if (i, m, n) in cache:\n",
    "            return cache[(i, m, n)]\n",
    "\n",
    "        if i < 0:\n",
    "            cache[(i, m, n)] = 0\n",
    "            return 0\n",
    "\n",
    "        n0, n1 = counter[i][\"0\"], counter[i][\"1\"]\n",
    "        if n0 > m or n1 > n:\n",
    "            cache[(i, m, n)] = self.recur(counter, cache, i - 1, m, n)\n",
    "            return cache[(i, m, n)]\n",
    "\n",
    "        cache[(i, m, n)] = max(\n",
    "            self.recur(counter, cache, i - 1, m, n),\n",
    "            self.recur(counter, cache, i - 1, m - n0, n - n1) + 1,\n",
    "        )\n",
    "        return cache[(i, m, n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        N=len(strs)\n",
    "        @cache\n",
    "        def dfs(i,m,n):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            counter=Counter(strs[i])\n",
    "            one=counter['1']\n",
    "            zero=counter['0']\n",
    "            if m>=zero and n>=one:\n",
    "                return max(dfs(i-1,m,n),dfs(i-1,m-zero,n-one)+1)\n",
    "            return dfs(i-1,m,n)\n",
    "        return dfs(N-1,m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        @functools.cache\n",
    "        def dfs(i, m_i, n_i):\n",
    "            if i == len(strs) or m_i < 0 or n_i < 0:\n",
    "                return 0\n",
    "\n",
    "            s = strs[i]\n",
    "            c_s = Counter(s)\n",
    "            n_zeros = c_s[\"0\"]\n",
    "            n_ones = c_s[\"1\"]\n",
    "\n",
    "            val1, val2 = 0, 0\n",
    "            if n_zeros <= m_i and n_ones <= n_i:\n",
    "                val1 = dfs(i + 1, m_i - n_zeros, n_i - n_ones) + 1\n",
    "            \n",
    "            val2 = dfs(i + 1, m_i, n_i)\n",
    "\n",
    "            return max(val1, val2)\n",
    "\n",
    "        return dfs(0, m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def findmf(kkk, m, n):\n",
    "            if m < 0 or n < 0:\n",
    "                return -float('inf')\n",
    "            if kkk==0: return 0\n",
    "            strs_ = strs[-kkk:]\n",
    "            t = strs_[0]\n",
    "            # op1 choose\n",
    "            md = t.count('0') \n",
    "            nd = t.count('1') \n",
    "            r1 = findmf(kkk-1, m-md, n-nd) + 1\n",
    "            # op2\n",
    "            r2 = findmf(kkk-1, m, n) + 0\n",
    "            return max(r1, r2)\n",
    "\n",
    "\n",
    "        return findmf(len(strs), m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        @cache\n",
    "        def f(index, mm, nn, num):\n",
    "            if mm > m or nn > n:\n",
    "                return 0\n",
    "            if index == len(strs):\n",
    "                return num\n",
    "            tm = tn = 0\n",
    "            for i in strs[index]:\n",
    "                if i == '1':\n",
    "                    tn += 1\n",
    "                elif i == '0':\n",
    "                    tm += 1\n",
    "            return max(f(index+1, mm, nn, num), f(index+1, mm+tm, nn+tn, num+1))\n",
    "        \n",
    "        res = f(0, 0, 0, 0)\n",
    "        f.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "\n",
    "        sts = [[st.count(\"0\"),st.count(\"1\")] for st in strs]\n",
    "        dp = [[[-1 for p in range(len(sts))] for j in range(n+1)] for i in range(m+1)]\n",
    "        \n",
    "        def dfs(m,n,p):\n",
    "            if p==len(sts) or (m==0 and n==0):\n",
    "                return 0\n",
    "            if dp[m][n][p]>=0:\n",
    "                return dp[m][n][p]\n",
    "            ans = dfs(m,n,p+1)\n",
    "            if sts[p][0]<=m and sts[p][1]<=n:\n",
    "                ans=max(ans,1+dfs(m-sts[p][0],n-sts[p][1],p+1))\n",
    "            dp[m][n][p]=ans\n",
    "            return ans\n",
    "        \n",
    "        return dfs(m,n,0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        \n",
    "        memory_dict = {}\n",
    "        def dfs(index, left_m, left_n):\n",
    "            if index < 0:\n",
    "                return 0\n",
    "\n",
    "            if (index, left_m, left_n) in memory_dict:\n",
    "                return memory_dict[(index, left_m, left_n)]\n",
    "            \n",
    "            count_dict = collections.Counter(strs[index])\n",
    "            res1 = dfs(index - 1, left_m, left_n)\n",
    "            if left_m - count_dict['0'] >= 0 and left_n - count_dict['1'] >= 0:\n",
    "                res2 = dfs(index - 1, left_m - count_dict['0'], left_n - count_dict['1']) + 1\n",
    "            else:\n",
    "                res2 = -1\n",
    "            \n",
    "            memory_dict[(index, left_m, left_n)] = max(res1, res2)\n",
    "            return memory_dict[(index, left_m, left_n)]\n",
    "        \n",
    "        return dfs(len(strs) - 1, m, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        length = len(strs)\n",
    "        dp = [[[0]*(n+1) for i in range(m+1)]*(m+1) for i in range(length+1)]\n",
    "        for i in range(1, length+1):\n",
    "            zerosOnes = self.getZerosOnes(strs[i-1])\n",
    "            zeros, ones = zerosOnes[0], zerosOnes[1]\n",
    "            for j in range(0, m+1):\n",
    "                for k in range(0, n+1):\n",
    "                    if j >= zeros and k >= ones:\n",
    "                        dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones]+1)\n",
    "                    else:\n",
    "                        dp[i][j][k] = dp[i-1][j][k]\n",
    "        return dp[length][m][n]\n",
    "\n",
    "\n",
    "    def getZerosOnes(self, str_list):\n",
    "        zerosOnes = [0]*2\n",
    "        length = len(str_list)\n",
    "        for i in range(length):\n",
    "            if str_list[i] == '0':\n",
    "                zerosOnes[0] += 1\n",
    "            elif str_list[i] == '1':\n",
    "                zerosOnes[1] += 1\n",
    "        return zerosOnes\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        N = len(strs)\n",
    "        @cache\n",
    "        def dfs(idx, cnt, mleft, nleft):\n",
    "            if idx == N:\n",
    "                return cnt\n",
    "            c = Counter(strs[idx])\n",
    "            ret = dfs(idx+1, cnt, mleft, nleft)\n",
    "            if mleft >= c['0'] and nleft >= c['1']:\n",
    "                # print(strs[idx], c, cnt, mleft, nleft)\n",
    "                ret = max(ret, dfs(idx+1, cnt+1, mleft-c['0'], nleft-c['1']))\n",
    "            return ret\n",
    "        return dfs(0, 0, m, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i: int, cnt0: int, cnt1: int) -> int:\n",
    "            if i == len(strs):\n",
    "                return 0\n",
    "            counter = collections.Counter(strs[i])\n",
    "            ret = dfs(i + 1, cnt0, cnt1)\n",
    "            if cnt0 + counter['0'] <= m and cnt1 + counter['1'] <= n:\n",
    "                ret = max(ret, dfs(i + 1, cnt0 + counter['0'], cnt1 + counter['1']) + 1)\n",
    "            return ret\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        l = len(strs)\n",
    "        @cache\n",
    "        def dfs(i, mn):\n",
    "            m, n = mn\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            last_0 = m - strs[i].count('0')\n",
    "            last_1 = n - strs[i].count('1')\n",
    "            if last_0 < 0 or last_1 < 0:\n",
    "                return dfs(i-1, mn)\n",
    "            return max(dfs(i-1, mn), dfs(i-1, (last_0, last_1))+ 1)\n",
    "\n",
    "        return dfs(l - 1, (m, n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,c):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            c0 = strs[i].count(\"0\")\n",
    "            c1 = len(strs[i]) - c0\n",
    "            if c0>c[0] or c1>c[1]:\n",
    "                return dfs(i-1,c)\n",
    "            return max(dfs(i-1,c),dfs(i-1,(c[0]-c0,c[1]-c1,))+1)\n",
    "        return dfs(len(strs)-1,(m,n,))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        def tell(s):\n",
    "            c = Counter(s)\n",
    "            return (c['0'],c['1'])\n",
    "        \n",
    "\n",
    "        for i, j in enumerate(strs):\n",
    "            strs[i] = tell(j)\n",
    "        @cache\n",
    "        def find(i, res, res1):\n",
    "            if i == len(strs):\n",
    "                return res1\n",
    "            if res[0]+strs[i][0] <= m and res[1] + strs[i][1] <= n:\n",
    "                res_t = (res[0]+strs[i][0], res[1] + strs[i][1])\n",
    "                return max(find(i+1, res, res1), find(i+1, res_t, res1 + 1))\n",
    "            else:\n",
    "                return find(i+1, res, res1)\n",
    "        return find(0,(0,0),0)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        l=len( strs )  \n",
    "        def g( i):\n",
    "            tmp = strs[i]\n",
    "            a,b =0,0\n",
    "            for i in tmp :\n",
    "                if i=='0':\n",
    "                    a+=1 \n",
    "                else:\n",
    "                    b+=1 \n",
    "            return [a,b  ]\n",
    "        self.ans = 0 \n",
    "        @cache \n",
    "        def dfs( j, a ,b  ):\n",
    "            if j==l :\n",
    "                return 0 \n",
    "            tmp=g( j )\n",
    "            if ( tmp[0] >a) or ( tmp[1] > b ) :\n",
    "                return dfs( j+1,  a,b ) \n",
    "            else:\n",
    "                ans = max( dfs( j+1, a,b) , 1+dfs( j+1, a-tmp[0], b-tmp[1])) \n",
    "                return ans \n",
    "        return dfs( 0, m,n )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.source = []\n",
    "        self.m = 0\n",
    "        self.n = 0\n",
    "        self.A = {}\n",
    "\n",
    "    def findMaxForm(self, str, m, n):\n",
    "        source = []\n",
    "        for s in str:\n",
    "            i = 0\n",
    "            j = 0\n",
    "            for c in s:\n",
    "                if c == '0':\n",
    "                    i = i + 1\n",
    "                else:\n",
    "                    j = j + 1\n",
    "            if i <= m and j <= n:\n",
    "                source.append((i, j))\n",
    "\n",
    "        length = len(source)\n",
    "        self.source = source\n",
    "        self.m = m\n",
    "        self.n = n\n",
    "\n",
    "        A = {}\n",
    "        x = 0\n",
    "        y = 0\n",
    "        A[(0, 0, 0)] = 0\n",
    "        for k in range(0, length):\n",
    "            x = x + source[k][0]\n",
    "            y = y + source[k][1]\n",
    "            A[(0, x, y)] = 0\n",
    "\n",
    "        for k in range(0, length):\n",
    "            A[(k + 1, 0, 0)] = 0\n",
    "\n",
    "        ix = 0\n",
    "        iy = 0\n",
    "        for k in range(0, length):\n",
    "            x = 0\n",
    "            y = 0\n",
    "            for t in range(0, length):\n",
    "                A[(k + 1, x + source[t][0], y + source[t][1])] = max(A[(k, x + source[t][0], y + source[t][1])],\n",
    "                                                                     1 + A[(k, x, y)])\n",
    "                x = x + source[t][0]\n",
    "                y = y + source[t][1]\n",
    "\n",
    "        return self.find(length, m, n)\n",
    "\n",
    "    def find(self, k, x, y):\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            if (k, x, y) in self.A:\n",
    "                return self.A[(k, x, y)]\n",
    "            result = 0\n",
    "            if self.source[k - 1][0] <= x and self.source[k - 1][1] <= y:\n",
    "                result = max(self.find(k - 1, x, y),\n",
    "                           1 + self.find(k - 1, x - self.source[k - 1][0], y - self.source[k - 1][1]))\n",
    "            else:\n",
    "                result = self.find(k - 1, x, y)\n",
    "            self.A[(k, x, y)] = result\n",
    "            return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,one,zero):\n",
    "            if i == len(strs) or m+n == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                res = dfs(i+1,one,zero)\n",
    "                cnt = Counter(strs[i])\n",
    "                if (one - cnt['1'] )>=0 and( zero - cnt['0']) >=0:\n",
    "                    res = max(res,dfs(i+1, one - cnt['1'] , zero - cnt['0'])+1)\n",
    "                return res\n",
    "        return dfs(0,n,m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        lens = len(strs)\n",
    "\n",
    "        res = 0\n",
    "        data = []\n",
    "        for item in strs:\n",
    "            data.append((item.count(\"0\"), item.count(\"1\")))\n",
    "\n",
    "        func_set = set()\n",
    "\n",
    "        def func(idx=0, zero=0, one=0, length=0):\n",
    "            if zero > m or one > n:\n",
    "                return\n",
    "            nonlocal res\n",
    "            if idx >= lens:\n",
    "                if length > res:\n",
    "                    res = length\n",
    "                return\n",
    "            key = \"%d_%d_%d_%d\" % (idx + 1, zero, one, length)\n",
    "            if key in func_set:\n",
    "                return\n",
    "\n",
    "            func(idx + 1, zero + data[idx][0], one + data[idx][1], length + 1)\n",
    "            func(idx + 1, zero, one, length)\n",
    "\n",
    "            func_set.add(key)\n",
    "            \n",
    "\n",
    "        func()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        counters = [Counter(s) for s in strs]\n",
    "        nStrs = len(strs)\n",
    "        res = 0\n",
    "        @cache\n",
    "        def dfs(m, n, i, k):\n",
    "            nonlocal res\n",
    "            if i == len(strs):\n",
    "                res = max(res, k)\n",
    "                return\n",
    "            counter = counters[i]\n",
    "            if m >= counter['0'] and n >= counter['1']:\n",
    "                if k+1 + (nStrs-(i+1)) > res:\n",
    "                    dfs(m-counter['0'], n-counter['1'], i+1, k+1)\n",
    "            if k + (nStrs-(i+1)) > res:\n",
    "                dfs(m,n,i+1,k)\n",
    "        dfs(m, n, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        count = [Counter(s) for s in strs]\n",
    "        @cache\n",
    "        def dfs(m, n, i):\n",
    "            if i < 0 or (not m and not n):\n",
    "                return 0\n",
    "            elif m < (M := count[i]['0']) or n < (N := count[i]['1']):\n",
    "                return dfs(m, n, i - 1)\n",
    "            else:\n",
    "                return max(dfs(m, n, i - 1), 1 + dfs(m - M, n - N, i - 1))\n",
    "        return dfs(m, n, len(strs) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,m,n):\n",
    "            if i==0:\n",
    "                if m>=ms[0] and n>=ns[0]:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if m==0 and n==0:\n",
    "                return 0\n",
    "            if ms[i]<=m and ns[i]<=n:\n",
    "                return max(dfs(i-1,m,n),dfs(i-1,m-ms[i],n-ns[i])+1)\n",
    "            else:\n",
    "                return dfs(i-1,m,n)\n",
    "\n",
    "        ms, ns = [], []\n",
    "        for s in strs:\n",
    "            x = len([c for c in s if c == '0'])\n",
    "            if x > m or len(s) - x > n:\n",
    "                continue\n",
    "            ms.append(x)\n",
    "            ns.append(len(s) - x)\n",
    "        if len(ms) == 0:\n",
    "            return 0\n",
    "        tmp=list(zip(*map(list,sorted(zip(ms,ns),reverse=True))))\n",
    "        # print(tmp)\n",
    "        ms,ns=tmp[0],tmp[1]\n",
    "        return dfs(len(ms)-1,m,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "class Solution:\r\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\r\n",
    "        L=len(strs)\r\n",
    "        count=[[0,0] for _ in range(L)]\r\n",
    "        for i in range(L):\r\n",
    "            z,o=0,0\r\n",
    "            for c in strs[i]:\r\n",
    "                if c=='0':\r\n",
    "                    z+=1\r\n",
    "                else:\r\n",
    "                    o+=1\r\n",
    "            count[i][0]=z\r\n",
    "            count[i][1]=o\r\n",
    "        \r\n",
    "        count.sort(key=lambda x:(x[0],x[1]))\r\n",
    "        \r\n",
    "        # ret=0\r\n",
    "        @cache\r\n",
    "        def pick(m,n,index):\r\n",
    "            # nonlocal ret\r\n",
    "            if index==L:\r\n",
    "                return 0\r\n",
    "        \r\n",
    "            z,o=count[index]\r\n",
    "            zz=m-z\r\n",
    "            oo=n-o\r\n",
    "            ret=0\r\n",
    "            if zz>=0 and oo>=0:\r\n",
    "                ret=1+pick(zz,oo,index+1)\r\n",
    "            if zz<0 and oo<0:\r\n",
    "                return ret\r\n",
    "            return max(ret,pick(m,n,index+1))\r\n",
    "        return pick(m,n,0)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        c = []\n",
    "        for s in strs:\n",
    "            c.append(Counter(s))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def f(m, n, i):\n",
    "            if (m <= 0 and n <= 0) or i < 0:\n",
    "                return 0\n",
    "            count = c[i]\n",
    "            if m < count['0'] or n < count['1']:\n",
    "                return f(m, n, i-1)\n",
    "            return max(f(m, n, i-1), 1+f(m-count['0'], n-count['1'], i-1))\n",
    "        return f(m, n, len(strs) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        cnt = [Counter(s) for s in strs]\n",
    "        N = len(strs)\n",
    "        @cache\n",
    "        def dfs(i,m,n):\n",
    "            if (m == 0 and n == 0) or i == N:\n",
    "                return 0\n",
    "            x,y = cnt[i]['0'],cnt[i]['1']\n",
    "            if x <= m and y <= n:\n",
    "                return max(1 + dfs(i + 1,m - x,n - y),dfs(i + 1,m,n))\n",
    "            return dfs(i + 1,m,n)\n",
    "        return dfs(0,m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        l = len(strs)\n",
    "        cnts = [Counter(s) for s in strs]\n",
    "        @cache\n",
    "        def dfs(i, rm, rn):\n",
    "            if i == l:\n",
    "                return 0\n",
    "  \n",
    "            cnt = cnts[i]\n",
    "            ans = dfs(i+1, rm, rn)\n",
    "            if cnt['0'] <= rm and cnt['1'] <= rn:\n",
    "                ans = max(ans, dfs(i+1, rm - cnt['0'], rn - cnt['1']) + 1)\n",
    "            \n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, m, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        # 思路：记忆化搜索+深度优先搜索\n",
    "        memo = {}\n",
    "        # 记录strs里面每个str的'0','1'个数\n",
    "        length = len(strs)\n",
    "        couples = [[0,0] for i in range(length)]\n",
    "        for i in range(length):\n",
    "            for char in strs[i]:\n",
    "                couples[i][int(char)] += 1\n",
    "        \n",
    "        # 深度优先搜索\n",
    "        def dfs(m_,n_,idx):\n",
    "            key = (m_ << 17) ^ (n_<< 10) ^ idx\n",
    "            # 剪枝\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "\n",
    "            # 终止搜索\n",
    "            if m_ < 0 or n_ < 0 or idx == length:\n",
    "                memo[key] = 0\n",
    "                return 0\n",
    "            \n",
    "            # 继续搜索\n",
    "            ans1 = 0\n",
    "            if couples[idx][0] <= m_ and couples[idx][1] <= n_:\n",
    "                ans1 = 1 + dfs(m_-couples[idx][0],n_-couples[idx][1],idx+1)\n",
    "            ans2 = dfs(m_,n_,idx+1)\n",
    "            # 更新memo\n",
    "            memo[key] = max(ans1,ans2)\n",
    "            return memo[key]\n",
    "        \n",
    "        \n",
    "        return dfs(m,n,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        # dp[i][j][k]代表前 i 个str组合的子集\"恰好\"组成 m 个 0 和 n 个 1 的最大长度\n",
    "        Len = len(strs)\n",
    "        dp = [ [ [ -1_000_000_000 for _ in range(n + 1) ] for _ in range(m + 1) ] for _ in range(Len + 1) ] # 初始化所有状态为非法\n",
    "        for i in range(Len + 1):\n",
    "            dp[i][0][0] = 0\n",
    "        # dp[0~Len][0][0]只能选空集，最大长度都为0\n",
    "        \n",
    "        for i in range(1, Len + 1):\n",
    "            zeros, ones = strs[i -1].count('0'), strs[i - 1].count('1')\n",
    "            for j in range(m + 1):\n",
    "                for k in range(n + 1):\n",
    "                    dp[i][j][k] = dp[i - 1][j][k]\n",
    "                    preJ, preK = j - zeros, k - ones\n",
    "                    if preJ >= 0 and preK >= 0:\n",
    "                        dp[i][j][k] = max(dp[i - 1][preJ][preK] + 1, dp[i][j][k])\n",
    "        \n",
    "        maxLen = -1_000_000_000\n",
    "        for j in range(m + 1):\n",
    "            for k in range(n + 1):\n",
    "                maxLen = max(maxLen, dp[Len][j][k])\n",
    "\n",
    "        return maxLen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        lst = sorted([(x.count(\"0\"), x.count(\"1\")) for x in strs])\n",
    "        @cache\n",
    "        def f(idx, x, y):\n",
    "            if idx >= len(lst):\n",
    "                return 0\n",
    "            if lst[idx][0] > x:\n",
    "                return 0\n",
    "            if lst[idx][1] <= y:\n",
    "                return max(1+f(idx+1, x-lst[idx][0], y-lst[idx][1]),f(idx+1, x, y) )\n",
    "            return f(idx+1, x, y)\n",
    "        return f(0, m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        mem = []\n",
    "        for i in strs:\n",
    "            mem.append(collections.Counter(i))        \n",
    "        \n",
    "        # 使用strs前i个元素，在小于n个零，m个一的情况下，可以获取的子集的最大个数\n",
    "        @lru_cache(None)\n",
    "        def dp(i,n,m):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            counter = mem[i]\n",
    "            num_zero,num_one = counter['0'],counter['1']\n",
    "            if num_zero>n or num_one>m:\n",
    "                return dp(i-1,n,m)\n",
    "            # elif num_zero<=n and num_one<=m:\n",
    "            else:\n",
    "                return max(dp(i-1,n-num_zero,m-num_one)+1,dp(i-1,n,m))\n",
    "        \n",
    "        return dp(len(strs)-1,m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        s = len(strs)\n",
    "        # 统计每个字符串 0 1 的数量\n",
    "        pre = [[0, 0] for i in range(s)]\n",
    "        for i in range(s):\n",
    "            x, y = 0, 0\n",
    "            for ss in strs[i]:\n",
    "                if ss == '0':\n",
    "                    x += 1\n",
    "                else:\n",
    "                    y += 1\n",
    "            pre[i][0], pre[i][1] = x, y\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, m, n):\n",
    "            if not i < s:\n",
    "                return 0\n",
    "            if m >= pre[i][0] and n >= pre[i][1]:\n",
    "                return max(dfs(i + 1, m, n), dfs(i + 1, m - pre[i][0], n - pre[i][1]) + 1)\n",
    "            else:\n",
    "                return dfs(i + 1, m, n)\n",
    "\n",
    "        return dfs(0, m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        from collections import Counter\n",
    "        N, S = len(strs), [Counter(s) for s in strs]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, rm, rn):\n",
    "            if i == N: return 0\n",
    "\n",
    "            v1, v2 = dfs(i + 1, rm, rn), float('-inf')\n",
    "            if rm >= S[i]['0'] and rn >= S[i]['1']:\n",
    "                v2 = 1 + dfs(i + 1, rm - S[i]['0'], rn - S[i]['1'])\n",
    "\n",
    "            return max(v1, v2)\n",
    "\n",
    "        return dfs(0, m, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        c = [Counter(item) for item in strs]\n",
    "        length = len(strs)\n",
    "        @lru_cache(None)\n",
    "        def dfs(index, count0, count1):\n",
    "            if index == length: return 0\n",
    "\n",
    "            # 能够取的情况下分两种 取还是不取 要最大的\n",
    "            if c[index]['0'] + count0 <= m and c[index]['1'] + count1 <= n:\n",
    "                return max(dfs(index + 1, count0, count1), 1 + dfs(index + 1, count0 + c[index]['0'], count1 + c[index]['1']))\n",
    "            # 不能够取 只能向下递归\n",
    "            else:\n",
    "                return dfs(index + 1, count0, count1)\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: list, m: int, n: int) -> int:\n",
    "        nums=[[0,0]for num in range(len(strs))]\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(len(strs[i])):\n",
    "                if strs[i][j]=='0' :\n",
    "                    nums[i][0]+=1\n",
    "                else:\n",
    "                    nums[i][1]+=1\n",
    "        dp=[ [ [-1 for k in range(n)] for j in range(m)] for i in range(len(strs)+1)]\n",
    "        for i in range(len(dp[0])):\n",
    "            for j in range(len(dp[0][i])):\n",
    "                dp[0][i][j]=0\n",
    "        notation=[ [ [-1 for k in range(n)] for j in range(m)] for i in range(len(strs))]\n",
    "        @functools.lru_cache(None)\n",
    "        def knapsack(k:int,M:int,N:int):\n",
    "            if dp[k][M-1][N-1]!=-1:\n",
    "                return dp[k][M-1][N-1]\n",
    "            else:\n",
    "                take=-1\n",
    "                if M>=nums[k-1][0] and N>=nums[k-1][1]:\n",
    "                    take=knapsack(k-1,M-nums[k-1][0],N-nums[k-1][1])+1\n",
    "                untake=knapsack(k-1,M,N)\n",
    "                if untake>take:\n",
    "                    notation[k-1][M-1][N-1]=0\n",
    "                    return untake\n",
    "                else:\n",
    "                    notation[k-1][M-1][N-1]=1\n",
    "                    return take\n",
    "        return knapsack(len(strs),m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        l = len(strs)\n",
    "        # cnt = [0] * l\n",
    "        # for i, x in enumerate(strs):\n",
    "        #     cnt[i] = x.count(\"0\")\n",
    "        # @cache\n",
    "        # #0/1背包 容积有两个:\n",
    "        # def dfs(i: int, x: int, y: int) -> int:\n",
    "        #     #boundary\n",
    "        #     if i < 0:\n",
    "        #         return -inf if (x < 0 or y < 0) else 0\n",
    "        #     #val_return:\n",
    "        #     #where\n",
    "        #     s = strs[i]\n",
    "        #     cnt1 = cnt[i]\n",
    "        #     cnt2 = len(s) - cnt1\n",
    "        #     if x - cnt1 < 0 and y - cnt2 < 0:\n",
    "        #         return dfs(i - 1, x, y)\n",
    "        #     return max(dfs(i - 1, x, y), dfs(i - 1, x - cnt1, y - cnt2) + 1)\n",
    "        #entrance\n",
    "        # return dfs(l - 1, m, n)\n",
    "        cnt = [0] * l\n",
    "        for i, x in enumerate(strs):\n",
    "            cnt[i] = x.count(\"0\")\n",
    "        f = [[[-inf] * (n + 109) for _ in range(m + 109)] for _ in range(l + 1)]\n",
    "        for j in range(m + 1):\n",
    "            for k in range(n + 1):\n",
    "                f[0][j][k] = 0\n",
    "        for i in range(l):\n",
    "            for x in range(m + 1):\n",
    "                for y in range(n + 1):\n",
    "                    s = strs[i]\n",
    "                    cnt1 = cnt[i]\n",
    "                    cnt2 = len(s) - cnt1\n",
    "                    if x - cnt1 < 0 and y - cnt2 < 0:\n",
    "                        f[i + 1][x][y] = f[i][x][y]\n",
    "                    else:\n",
    "                        f[i + 1][x][y] = max(f[i][x][y], f[i][x - cnt1][y - cnt2] + 1)\n",
    "        return f[l][m][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, ss: List[str], m: int, n: int) -> int:\n",
    "        l=len(ss)\n",
    "        a,b=[0]*l,[0]*l\n",
    "        for i in range(l):\n",
    "            s=ss[i]\n",
    "            for c in s:\n",
    "                if c=='1':\n",
    "                    b[i]+=1\n",
    "                else:\n",
    "                    a[i]+=1\n",
    "        dp=[[[float('-inf')]*(n+1) for _ in range(m+1)] for _ in range(l)]\n",
    "        dp[0][0][0]=0\n",
    "        if a[0]<=m and b[0]<=n:\n",
    "            dp[0][a[0]][b[0]]=1\n",
    "        for i in range(1,l):\n",
    "            a0=a[i]\n",
    "            b0=b[i]\n",
    "            for j in range(m+1):\n",
    "                for k in range(n+1):\n",
    "                    dp[i][j][k]=dp[i-1][j][k]\n",
    "                    if j-a0>=0 and k-b0>=0:\n",
    "                        dp[i][j][k]=max(dp[i-1][j-a0][k-b0]+1,dp[i][j][k])\n",
    "        res=0\n",
    "        for j in range(m+1):\n",
    "            for k in range(n+1):\n",
    "                res=max(res,dp[-1][j][k])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        max_n = len(strs)\n",
    "        items = list(map(lambda s: (s.count('0'), s.count('1')), strs))\n",
    "\n",
    "        @functools.lru_cache(maxsize=100000)\n",
    "        def dfs(_u: int, _m: int, _n: int) -> int:\n",
    "            if _m < 0 or _n < 0:\n",
    "                return -1\n",
    "            if _u == max_n:\n",
    "                return 0\n",
    "            # 不选\n",
    "            _p = dfs(_u + 1, _m, _n)\n",
    "            # 选\n",
    "            _q = dfs(_u + 1, _m - items[_u][0], _n - items[_u][1])\n",
    "\n",
    "            return _p if _q == -1 else max(_q + 1, _p)\n",
    "\n",
    "        return dfs(0, m, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        # 转换成0，1的个数元组组成的数组\n",
    "        # 字典+子集\n",
    "        mm = {}\n",
    "        def makeKey(m, n):\n",
    "            return str(m) + \":\" + str(n)\n",
    "        def help(arr, m, n, start):\n",
    "            if start in mm:\n",
    "                if makeKey(m, n) in mm[start]:\n",
    "                    return mm[start][makeKey(m, n)]\n",
    "            if start > len(arr) - 1:\n",
    "                return 0\n",
    "            m_, n_ = arr[start]\n",
    "            ans = 0\n",
    "            if m_ <= m and n_ <= n:\n",
    "                ans = max(ans, help(arr, m - m_, n - n_, start + 1) + 1)\n",
    "            ans = max(ans, help(arr, m, n, start + 1))\n",
    "            if start not in mm:\n",
    "                mm[start] = {}\n",
    "            mm[start][makeKey(m, n)] = ans\n",
    "            return ans\n",
    "        arr = []\n",
    "        for x in strs:\n",
    "            N = len(x)\n",
    "            cnt = 0\n",
    "            for i in range(N):\n",
    "                if x[i] == '1':\n",
    "                    cnt += 1\n",
    "            m_ = N - cnt\n",
    "            n_ = N - m_\n",
    "            if m_ <= m and n_ <= n:\n",
    "                arr.append((m_, n_))\n",
    "        return help(arr, m, n, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        dp = [[[float(\"-inf\") for _ in range(n + 1)] for _ in range(m + 1)] for _ in range(len(strs) + 1)]\n",
    "        for i in range(len(strs) + 1):\n",
    "            dp[i][0][0] = 0\n",
    "        for j in range(m + 1):\n",
    "            for k in range(n + 1):\n",
    "                dp[0][j][k] = 0\n",
    "\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(m + 1):\n",
    "                for k in range(n + 1):\n",
    "                    zero = strs[i].count('0')\n",
    "                    one = strs[i].count('1')\n",
    "                    if zero <= j and one <= k:\n",
    "                        dp[i + 1][j][k] = max(dp[i][j][k], dp[i][j - zero][k - one] + 1)\n",
    "                    else:\n",
    "                        dp[i + 1][j][k] = dp[i][j][k]\n",
    "        return max(0, dp[-1][-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        # 初始化. \n",
    "        dp = [[[float(\"-inf\") for _ in range(n+1)] for _ in range(m+1)] for _ in range(len(strs))]\n",
    "        # 初始化 idx = 0. \n",
    "        str_0 = strs[0]\n",
    "        m_c, n_c = 0, 0\n",
    "        for c in str_0:\n",
    "            if c == \"0\":\n",
    "                m_c += 1\n",
    "            else:\n",
    "                n_c += 1\n",
    "        \n",
    "        if m-m_c >= 0 and n-n_c >= 0:\n",
    "            dp[0][m-m_c][n-n_c] = 1 \n",
    "        dp[0][m][n] = 0 \n",
    "\n",
    "\n",
    "        # 迭代. \n",
    "        for i in range(1, len(strs)):\n",
    "            m_c, n_c = 0, 0 \n",
    "            for c in strs[i]:\n",
    "                if c == \"0\":\n",
    "                    m_c += 1\n",
    "                else:\n",
    "                    n_c += 1\n",
    "            \n",
    "            for j in range(m+1):\n",
    "                for k in range(n+1):\n",
    "                    if j+m_c <= m and k+n_c <= n:\n",
    "                        dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j+m_c][k+n_c]+1)\n",
    "                    else:\n",
    "                        dp[i][j][k] = dp[i-1][j][k]\n",
    "            \n",
    "        return max([max(row) for row in dp[-1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        temp_mn = []\n",
    "        for s in strs:\n",
    "            num_one = sum(list(map(lambda x: int(x), list(s))))\n",
    "            temp_mn.append([len(s) - num_one, num_one])\n",
    "        import numpy\n",
    "        dp = numpy.zeros((len(strs), m+1, n+1)).tolist()\n",
    "        for i in range(temp_mn[0][0], len(dp[0])):\n",
    "            for j in range(temp_mn[0][1], len(dp[0][0])):\n",
    "                dp[0][i][j] = 1\n",
    "        for k in range(1, len(strs)):\n",
    "            for i in range(0, len(dp[0])):\n",
    "                for j in range(0, len(dp[0][0])):\n",
    "                    if i-temp_mn[k][0] >= 0 and j-temp_mn[k][1] >= 0:\n",
    "                        if dp[k-1][i][j] > dp[k-1][i-temp_mn[k][0]][j-temp_mn[k][1]]:\n",
    "                            dp[k][i][j] = dp[k-1][i][j]\n",
    "                        else:\n",
    "                            dp[k][i][j] = dp[k-1][i-temp_mn[k][0]][j-temp_mn[k][1]] + 1\n",
    "                    else:\n",
    "                        dp[k][i][j] = dp[k-1][i][j]\n",
    "        # print(dp)\n",
    "        return int(dp[-1][-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n",
    "        N=len(strs)\n",
    "        count=defaultdict(list)\n",
    "        for i,s in enumerate(strs):\n",
    "            c=Counter(s)\n",
    "            count[i]=[c['0'],c['1']]\n",
    "        \n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,m,n):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            one=count[i][1]\n",
    "            zero=count[i][0]\n",
    "            if m>=zero and n>=one:\n",
    "                return max(dfs(i-1,m,n),dfs(i-1,m-zero,n-one)+1)\n",
    "            return dfs(i-1,m,n)\n",
    "        return dfs(N-1,m,n)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
